package com.example.demo.leetcode.codetop.bytedance;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 * 输出：3
 * 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
 * 示例 2：
 *
 *
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 * 输出：5
 * 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
 * 示例 3：
 *
 * 输入：root = [1,2], p = 1, q = 2
 * 输出：1
 *  
 *
 * 提示：
 *
 * 树中节点数目在范围 [2, 105] 内。
 * -109 <= Node.val <= 109
 * 所有 Node.val 互不相同 。
 * p != q
 * p 和 q 均存在于给定的二叉树中。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/25 16:10
 */
public class 二叉树公共祖先 {


  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

  public class NodeInfo{

      boolean ispfather;
      boolean isqfather;

      public NodeInfo(boolean ispfather, boolean isqfather) {
          this.ispfather = ispfather;
          this.isqfather = isqfather;
      }
  }

  private int maxLevel = -1;
  private TreeNode res = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

      process(root,p,q,0);
      return res;
    }


    public NodeInfo process(TreeNode root, TreeNode p, TreeNode q,int level){

      if(root == null){
          return new NodeInfo(false,false);
      }
      boolean pfather;
      boolean qfather;

      NodeInfo leftInfo = process(root.left, p, q, level+1);
      NodeInfo rightInfo = process(root.right, p, q, level+1);
      pfather = (root.val == p.val) || leftInfo.ispfather ||rightInfo.ispfather;
      qfather = (root.val == q.val) || leftInfo.isqfather ||rightInfo.isqfather;
      if(pfather && qfather){
          if(level > maxLevel){
              maxLevel = level;
              res = root;
          }
      }
      return new NodeInfo(pfather,qfather);
    }



}
